home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12151 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.6 KB
  1. Path: detroit.freenet.org!ab411
  2. From: ab411@detroit.freenet.org (David R. Conrad)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: "Best fit" algorithm (help)
  5. Date: 29 Mar 1996 15:58:54 GMT
  6. Organization: Greater Detroit Free-Net, Detroit, MI
  7. Message-ID: <4jh1bu$rro@detroit.freenet.org>
  8. References: <APC&7'0'22b6b83'874@peg.apc.org>
  9. Reply-To: ab411@detroit.freenet.org (David R. Conrad)
  10. NNTP-Posting-Host: detroit.freenet.org
  11.  
  12.  
  13. In a previous article, riox@peg.apc.org () says:
  14. >I am looking for a "best fit" algorithm. 
  15. >The problem I have is very similar to finding the best way of fitting the 
  16. >maximum number of songs on (say) 45 minute tape.
  17. >If one knows the length of each song and the number of songs, how can one 
  18. >find the best arrangement to occupy maximum amount of tape without "cutting"
  19. >off any songs. Ie, how to minimise the empty space left on the tape.
  20.  
  21. This should probably be posted to comp.sci.algorithms, not comp.lang.c.
  22.  
  23. This is the knapsack problem, and if I recall correctly it is NP-complete.
  24. To find the best (optimal) fit, I think there is no known solution better
  25. than trying all possible arrangements of songs (no pun intended).
  26.  
  27. To find a good fit, I think a good algorithm would be to assign the longest
  28. songs to tapes first, then smaller songs, until you reach the smallest.
  29.  
  30. -- 
  31. David R. Conrad, conrad@detroit.freenet.org : PGP key on :  GDFN Hardware and
  32.    http://www.freenet.org/staff/conrad/     :  home page : Software Committee
  33. Union of Computer Hackers,  :  Is a tune greater than the hum of its parts?
  34. Local 2^859433-1 APL-CPIO   :    Is Twain more than the Sam of his parts?
  35.